In the reproduction of copies of an original document from video image data created, for example, by electronic raster input scanning from an original document, one is faced with the limited resolution capabilities of the reproducing system and the fact that output devices are mostly binary. This is particularly evident when attempting to reproduce halftones, lines and continuous tone images. Of course, an image data processing system may be tailored so as to offset the limited resolution capabilities of the reproducing apparatus used, but this is difficult due to the divergent processing needs required by the different types of image which may be encountered. In this respect, it should be understood that the image content of the original document may consist entirely of high frequency halftones, low frequency halftones, continuous tones, or line copy, or a combination, in some unknown degree, of some or all of the above. In the face of these possibilities, optimizing the image processing system for one image type in an effort to offset the limitations in the resolution capability of the reproducing apparatus used, may not be possible, requiring a compromise choice which may not produce acceptable results. Thus, for example, where one optimizes the system for low frequency halftones, it is often at the expense of degraded reproduction of high frequency halftones, or of line copy, and vice versa.
Color original documents, where all or part of the image is represented in one or more colors presents an additional challenge for segmentation. Typically, these images are defined in terms of Red-Green-Blue (RGB) color density signals, which represent image signals derived in scanning the image with intensity sensitive devices with appropriate color filters interposed in the path of light reflected thereto from the color document, or created on a document creating computer workstation. Each separation of the RGB color density signals requires processing in the same manner as the black and white images, e.g., continuous tone images required halftoning, halftoned images requires descreening and rescreening, and text/line art requires thresholding. This processing may occur after the image has been converted to the cyan-magenta-yellow (CMY) color density signals, that will ultimately provide driving signals for a color printer. Each separation could be processed separately with image segmentation algorithms, however, such parallel circuitry or processing is expensive in terms of hardware, and will require a downstream "separation reconciliation" process for handling inconsistent results at each separation.
As one example of the problems encountered, reproduction of halftoned images with screening tends to introduce moire, caused by the interaction of the original screen frequency and applied screen frequency. Although the use of high frequency line screens, as believed used in the Canon CLC500 Color Copier, can reduce the problem, the artifact can still occur in some images. In a networked environment particularly, it is desirable that the scanner detect the halftone and low pass filter the document image into a continuous tone for subsequent halftone reproduction by printers in the network in accordance with their particular capabilities.
In U.S. Pat. Ser. No. 08/004479 by Shiau, the question of whether a color image was scanned by a black and white capable scanner was addressed, so that color document reproduction on a black and white printer could be optimized. Not addressed was the problem of optimally reproducing color images for color originals, such as by, for example, the Xerox 5775 Color Copier, which includes a scanner for scanning color documents, a color document printer and associated processing for preparing scanned documents for printing.
In U.S. Pat. No. 4,194,221 to Stoffel, the problem of image segmentation was addressed by applying a discrimination function instructing the image processing system as to the type of image data present and particularly, an auto correlation function to the stream of pixel data, to determine the existence of halftone image data. Such a function is expressed as: ##EQU1## where n=the bit or pixel number;
p=the pixel voltage value; and PA1 t=the pixel position in the data stream. PA1 receiving from an image source a multi-separation document image and storing the multi-separation image in a data buffer; PA1 with a color space converter, converting the multi-separation document image received from the data buffer to a luminance-chrominance description of the document image, where one component thereof represents intensity of the document image; PA1 with an image segmentation circuit, receiving the intensity component of the document image and determining the image-type present in an area of the image therefrom; PA1 with a multi-image type image processor also receiving the multi-separation document image from the data buffer, processing a corresponding area of the multi-separation document image in accordance with the determined image type.
Stoffel describes a method of processing automatically a stream of image pixels representing unknown combinations of high and low frequency halftones, continuous tones, and/or lines to provide binary level output pixels representative of the image. The described function is applied to the stream of image pixels and, for the portions of the stream that contained high frequency halftone image data, notes a large number of closely spaced peaks in the resultant signal. The correlator circuits described in Stoffel's embodiment, however, are very expensive, as they must provide a digital multiplication function. Accordingly, as a practical matter, Stoffel requires as a first step, reduction of the amount of data handled, by initially thresholding image data against a single threshold value, to reduce the image to a high contrast black or white image. However, depending on the selection of the threshold as compared to the intensity of the image, significant amounts of information may be lost in the thresholding process. For example, if the threshold level is set to distinguish in the middle of the intensity range, but the image has significant variations through the darker gray levels, the thresholded result does not indicate the variations. This results in an undesirable loss of image information. While it may be possible to vary the threshold value adaptively from original to original and from image area to image area, such algorithms tend to be complicated and work well only for a restricted class of images such as line images. In U.S. Pat. No. 4,811,115 to Lin et al, the auto correlation function is calculated for the stream of halftone image data at selected time delays which are predicted to be indicative of the image frequency characteristics, without prior thresholding. The arithmetic function used in that auto correlation system is an approximation of the auto correlation function using logical functions and addition, rather than the multiplication function used in U.S. Pat. No. 4,194,221 to Stoffel. Valleys in the resulting auto correlated function are detected to determine whether high frequency halftone image data is present.
U.S. Pat. No. 08/004479 by Shiau is directed to the particular problem noted in the use of the auto correlation function of the false characterization of a portion of the image as a halftone, when in fact it would be preferable for the image to be processed as a line image. Examples of this defect are noted particularly in the processing of Japanese Kanji characters and small Roman letters. In these examples, the auto correlation function may detect the image as halftones and process accordingly, instead of applying a common threshold through the character image. The described computations of auto correlation are one dimensional in nature, and this problem of false detection will occur whenever a fine pattern that is periodic in the scan line or fast scan direction is detected, In the same vein, shadow areas and highlight areas are often not detected as halftones, and are then processed with the application of a uniform threshold.
GB 2,153,619A provides a similar determination of the type of image data. However in that case, a threshold is applied to the image data at a certain level, and subsequent to thresholding the number of transitions from light to dark within a small area is counted. The system operates on the presumption that data with a low number of transitions after thresholding is probably a high frequency halftone or continuous tone image. The thresholding step in this method has the same undesirable effect as described for Stoffel.
Of background interest in this area are U.S. Pat. No. 4,556,918 to Yamazaki et al. showing an arrangement assuming a periodicity of an area of halftone dots which are thresholded against an average value derived from the area to produce a density related video signal; U.S. Pat. No. 4,251,837 to Janeway, Ill. which shows the use of a three decision mode selection for determining threshold selection based on gradient constants for each pixel; U.S. Pat. No. 4,578,714 to Sugiura et al. which shows random data added to the output signal to eliminate pseudo-outlines; U.S. Pat. No. 4,559,563 to Joiner, Jr. suggests an adaptive prediction for compressing data based on a predictor which worked best for a previous pixel block; and U.S. Pat. No. 3,294,896 to Young, Jr. teaches the usefulness of thresholding in producing an image from a binary digital transmission system.
U.S. Pat. No. 4,509,195 to Nadler describes a method for binarization of a pattern wherein two concentric rings around a pixel are evaluated to determine contrast values, and the contrast values are used then to determine whether the pixel and the surrounding areas have a light or dark quality. U.S. Pat. No. 4,547,811 to Ochi et al. teaches a method of processing gray level values, depending on the density level of blocks of pixels, and their difference from a minimum or maximum value. The blocks are then processable by a halftone processing matrix depending on the difference value, U.S. Pat. No. 4,730,221 to Roetling discloses a screening technique where values of gray over an image are evaluated to determine a minimum and maximum level, in order to determine constant levels of gray. U.S. Pat. No. 4,736,253 to Shida discloses a method of producing a halftone dot by selectively comparing image signals with highlight and shadow reference values, for determination of the binarization process.
The patents cited herein are incorporated by reference for their teachings.